package shortestDistanceAfterQueries;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<List<Integer>> map = new ArrayList<>(n);
        for(int i=0; i < n; i+=1){
            List<Integer> dist = new ArrayList<>();
            dist.add(i+1);
            map.add(dist);
        }
        int[] res = new int[queries.length];
        for(int i = 0 ; i < queries.length; i +=1){
            //更新地图
            map.get(queries[i][0]).add(queries[i][1]);
            //搜索地图
            res[i] = search(map,n);
        }
        return res;
    }
    public int search(List<List<Integer>> map,int n){
        //定义一个数组记录到达每一个目的地需要的路径
        int[] dist = new int[n];
        //搜索地图计算路径
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        while(!q.isEmpty()){
            //起点
            int cur = q.poll();
            if (cur >= n-1){
                break;
            }
            //终点
            List<Integer> ends = map.get(cur);
            for (Integer end : ends) {
                if(dist[end] > 0){
                    continue;
                }
                dist[end] = dist[cur]+1;
                q.add(end);
            }
        }
        return dist[n-1];
    }


}
